//分割等和子集   力扣416
//01背包
class Solution {
public:
	bool canPartition(vector<int>& nums) {
		int sum = 0;
		for(int i = 0; i < nums.size(); i++)
			sum += nums[i];
		if(sum % 2 != 0) return false;
		int target = sum / 2;
		vector<int> dp(target+1);
		
		for(int i = nums[0]; i < dp.size(); i++)
			dp[i] = nums[0];
		
		for(int i = 1; i < nums.size(); i++)
		{
			for(int j = target; j >=nums[i]; j--)
			{
				dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
			}
		}
		if(dp[target] == target) return true;
		return false;
	}
};
